package com.salim.leetcode.$74;

import java.util.Arrays;

/**
 * 这道题还有一种解法是把整个矩阵看成一个链表 做一次二分查找 通过取模来解决换行的问题
 */
public class SearchA2DMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        //对第一列二分查找
        //如果相等直接返回
        //取小的那一行
        //对行二分查找
        int[] line;
        int i=0;
        int j=matrix.length-1;
        //超限
        if(target<matrix[i][0]||target>matrix[j][matrix[0].length-1]){
            return false;
        }
        while (i<j&&i+1<j){
            int mid =i + (j -i)/2;
            if(target<matrix[mid][0]){
                //左
                j = mid-1;
            }else if(target>matrix[mid][0]){
                i = mid;
            }else{
                return true;
            }
        }
        if(i==j){
            line = matrix[i];
        }else{
            //校验第一行
            if(i+1==j && target>=matrix[i][0]&&target<matrix[j][0]){
                line = matrix[i];
            }else{
                line = matrix[j];
            }
        }
        i=0;
        j=line.length-1;
        while (i<j){
            int mid =i + (j -i)/2;
            if(target<line[mid]){
                //左
                j = mid-1;
            }else if(target>line[mid]){
                i = mid+1;
            }else{
                return true;
            }
        }
        if(i==j&&line[i]==target){
            return true;
        }

        return false;
    }

    public static void main(String[] args){
        SearchA2DMatrix searchA2DMatrix = new SearchA2DMatrix();
        int[][] a = {{1,3,4,7},{10,11,16,20},{23,30,34,50}};
        searchA2DMatrix.searchMatrix(a,11);
    }
}
